package 动态规划.另类的;

import java.math.BigInteger;
import java.util.Scanner;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/3/9 14:39
 */
public class 魔法师 {

    /*
   魔法师小树有 n 个魔法元素，他把它们排成一行，从左到右第 i 个魔法元素的能量值是一个非零整数 a[i]
  。小树每次施展魔法的方式是挑选一段连续非空的魔法元素，将它们的能量值乘起来，得到值就是这次魔法的总能量。如果总能量大于零即为白魔法，否则为黑魔法。
   现在小树想知道施展一个白魔法或黑魔法的方案数分别有多少。两个方案不同是指挑选的连续区间不同。

    ==
    输入:
    5 -3 3 -1 1
    输出:
    8 7



作者：塔子
链接：https://leetcode.cn/circle/discuss/1qE7m2/
     */

    /*
         dp[i][0]:当前 以 i 开头的区间 对应的 白魔法数
    dp[i][1] : 当前 以 i 开头 的区间 黑魔法数

    如果a[i] > 0
    dp[i][0] = dp[i + 1][0] + 1;
    dp[i][1] = dp[i + 1][1] // 直接省略也可以

    如果 a[i] <  0
    int temp = dp[i][0];
     dp[i][0] = dp[i + 1][1];
    dp[i][1] = temp + 1;

     */
    public int[] solution(int nums[]){
        int white = nums[nums.length - 1] > 0 ? 1 : 0, black = white == 0 ? 1 : 0;
        int ansWhite = white, ansBlack = black;
        System.out.print(white + "  ");
        System.out.println(black);
        for(int i = nums.length - 2;i >= 0;i--){
            if(nums[i] > 0){
                white = white + 1;
            }
            else{ // nums[i] < 0
                int temp = white;
                white = black;
                black = temp + 1;
            }
            ansWhite += white;
            ansBlack += black;
            System.out.println(white + "  " + black);
        }
        return new int[]{ansWhite,ansBlack};
    }


    /*
     对数器
     */

    public int[] right(int nums[]){
        int ansA = 0;
        int ansB = 0;
        for(int i = 0;i < nums.length;i++){
            long temp = 1;
            for(int j = i;j < nums.length;j++){
                temp *= nums[j];
                if(temp > 0){
                    ansA ++;
                }
                else{
                    ansB++;
                }
            }
        }
        return new int[]{ansA,ansB};
    }
    /*
     上面的 暴力算法 ，过不了， 因为 溢出， 整型 溢出， long  也 溢出！
    对于全是  整数的 来说， 使用 double  会比下面的 BigInteger 更加好， 省空间啊！
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int nums[] = new int[n];
        for(int i = 0;i < n;i++){
            nums[i] = sc.nextInt();
        }
        int ansA = 0, ansB = 0;
        for(int  i = 0;i < n;i++){
            BigInteger muti = BigInteger.ONE;
            for(int j = i;j < n;j++){
                muti = muti.multiply(new BigInteger(String.valueOf(nums[j])));
                if(muti.compareTo(BigInteger.ZERO) > 0){
                    ansA ++;
                }else{
                    ansB++;
                }
            }
        }
        System.out.println(ansB + " " + ansA);
        dp(nums);
    }
    /*
     最上面的 是对下面 这个 dp 算法的一个空间优化的  版本！
     */
    public static void dp(int nums[] ){
        int len = nums.length;
        int dp[][] = new int[len + 1][2]; // dp[i][0] 表示 以 i开头的连续区间的 白魔法， 1 表示黑魔法
        int ansA = 0, ansB = 0;
        for(int i = len - 1;i >= 0;i--){
            if(nums[i] > 0){
                dp[i][0] = dp[i + 1][0] + 1;
                dp[i][1] = dp[i + 1][1];
            }else{
                dp[i][0] = dp[i + 1][1];
                dp[i][1] = dp[i + 1][0] + 1;
            }
            ansA += dp[i][0];
            ansB += dp[i][1];
        }
        System.out.println(ansB + " " + ansA);
    }



}
